Mirror descent

 ( Mathematical Optimization ) 

In mathematics, mirror descent is an iterative optimization algorithm for finding a local minimum of a differentiable function.

It generalizes algorithms such as gradient descent and multiplicative weights.

---

History Mirror descent was originally proposed by Nemirovski and Yudin in 1983.Arkadi Nemirovsky and David Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley & Sons, 1983

---

Motivation In gradient descent with the sequence of learning rates $(\backslash eta\_n)\_\{n\; \backslash geq\; 0\}$ applied to a differentiable function $F$, one starts with a guess $\backslash mathbf\{x\}\_0$ for a local minimum of $F,$ and considers the sequence $\backslash mathbf\{x\}\_0,\; \backslash mathbf\{x\}\_1,\; \backslash mathbf\{x\}\_2,\; \backslash ldots$ such that

$\backslash mathbf\{x\}\_\{n+1\}=\backslash mathbf\{x\}\_n-\backslash eta\_n\; \backslash nabla\; F(\backslash mathbf\{x\}\_n),\backslash \; n\; \backslash ge\; 0.$

This can be reformulated by noting that

$\backslash mathbf\{x\}\_\{n+1\}=\backslash arg\; \backslash min\_\{\backslash mathbf\{x\}\}\; \backslash left(F(\backslash mathbf\{x\}\_n)\; +\; \backslash nabla\; F(\backslash mathbf\{x\}\_n)^T\; (\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n)\; +\; \backslash frac\{1\}\{2\; \backslash eta\_n\}\backslash |\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n\backslash |^2\backslash right)$

In other words, $\backslash mathbf\{x\}\_\{n+1\}$ minimizes the first-order approximation to $F$ at $\backslash mathbf\{x\}\_n$ with added proximity term $\backslash |\backslash mathbf\{x\}\; -\; \backslash mathbf\{x\}\_n\backslash |^2$.

This squared Euclidean distance term is a particular example of a Bregman distance. Using other Bregman distances will yield other algorithms such as /ref>

---

Formulation We are given convex function $f$ to optimize over a convex set $K\; \backslash subset\; \backslash mathbb\{R\}^n$, and given some norm $\backslash |\backslash cdot\backslash |$ on $\backslash mathbb\{R\}^n$.

We are also given differentiable convex function $h\; \backslash colon\; \backslash mathbb\{R\}^n\; \backslash to\; \backslash mathbb\{R\}$, $\backslash alpha$-strongly convex with respect to the given norm. This is called the distance-generating function, and its gradient $\backslash nabla\; h\; \backslash colon\; \backslash mathbb\{R\}^n\; \backslash to\; \backslash mathbb\{R\}^n$ is known as the mirror map.

Starting from initial $x\_0\; \backslash in\; K$, in each iteration of Mirror Descent:

• Map to the dual space: $\backslash theta\_t\; \backslash leftarrow\; \backslash nabla\; h\; (x\_t)$
• Update in the dual space using a gradient step: $\backslash theta\_\{t+1\}\; \backslash leftarrow\; \backslash theta\_t\; -\; \backslash eta\_t\; \backslash nabla\; f(x\_t)$
• Map back to the primal space: $x\text{'}\_\{t+1\}\; \backslash leftarrow\; (\backslash nabla\; h)^\{-1\}(\backslash theta\_\{t+1\})$
• Project back to the feasible region $K$: $x\_\{t+1\}\; \backslash leftarrow\; \backslash mathrm\{arg\}\backslash min\_\{x\; \backslash in\; K\}D\_h(x||x\text{'}\_\{t+1\})$, where $D\_h$ is the Bregman divergence.

---

Extensions Mirror descent in the online optimization setting is known as Online Mirror Descent (OMD).

---

See also

• Gradient descent
• Multiplicative weight update method
• Hedge algorithm
• Bregman divergence

Post Comment